1. Field of the Invention
The present invention generally relates to shared resource management in multi-tasking or multi-processor data processing systems and, more particularly, to a way to efficiently monitor and manage locked ranges of addressed elements, where the requested ranges of addressed elements can overlap, in a shared resource such as peripheral equipment or a byte space of a file or memory.
2. Description of the Prior Art
It is common in a multi-tasking or a multi-processor data processing system to asynchronously or concurrently share resources such as files, tables or memory. Many shared resources, however, can consist of a unitary entity or a multiplicity of entities known as addressable elements. A major characteristic of the utilization of these shared resources is the ability to randomly access and share a portion of the addressable elements within the resource. A portion of the addressable elements is commonly referred to as a range and is described by a starting point, called the offset (e.g. from the initial address of the resource), and the number of contiguous elements desired, called the length of the range. A special case would be a range of one addressable element which is described by an offset and a length of one. Possible types of shared resources would include processors in a parallel processing element or array, indices or records in a database, bytes in a file or in memory, entries in a Direct Access Storage Device (DASD) arrangement or hardware such as a range of input/output (I/0) devices such as displays and/or printers.
In this general type of environment, there may be several programs or processes running on one or more processors. These processes typically run concurrently but do not have any knowledge of other processes which may be running on the same data processing system. More than one of these processes may need to access a shared resource at the same time. This is known as resource contention. In order to resolve such contention, the processes rely on the system control program to monitor and coordinate access to the resource. Depending on the type of addressed elements which may exist in the shared resource and the type of access required, predetermined rules must be made to apply to addressed elements which are accessed or to which access is sought at a given time. For instance, if the shared resource is a database, access may be desired to be exclusive for read/write access or where different operating systems (e.g. DOS.TM., UNIX.TM., OS/2.TM.) may be in use at the same time, or access may be desired to be shared, for example, for read only access. With respect to a database, such accesses are referred to as locks. However, for clarity, each different type of access and, correspondingly, each set of rules which are to be applied for each type of access will be referred to as a state or state information. Therefore, exclusive access and shared access would be two distinct states of a lock.
System control programs including operating systems such as UNIX.TM. (a trademark of AT&T Bell Labs.) and IBM Corp.'s MVS (for Multiple Virtual Storage) provide files that consist of strings of bytes. These files in turn may be shared by multiple processes. Typically, the processes read and change only parts of the file. In order to insure the integrity of the file contents, it is necessary to assure that no two processes change the same data at the same time. At a minimum, a facility that allows voluntary locking of ranges of data is needed that will provide for exclusive use of data. Requests to lock a range of bytes would specify the first and last bytes to be locked. If the request was in the form of offset (e.g.first byte) and length, then the last byte could be computed.
General information on operating systems and, in particular, may be had by reference to Chapter 12 of the text book by Harold Lorin and Harvey M. Deitel entitled Operating Systems, published by Addison-Wesley Publishing Co. (1981). Specific information about the UNIX.TM. operating system may be had by reference to the book by Brian W. Kernigham and Rob Pike entitled The UNIX Proqramming Environment, published by Prentice-Hall, Inc. (1984). Specific information about the MVS operating system may be had by reference to Chapter 21 of the text book by Harvey M. Dietel entitled An Introduction to Operating Systems, published by Addison-Wesley Publishing Co. (1984). UNIX.TM. systems are also described in Chapter 18 of the Dietel text book.
Lock requests have been processed by a number of differing techniques in the past. The most difficult problem that is posed by addressable element range locking is that overlapping range lock requests may occur. For example, one lock request might hold addressable elements 6 and 7 and another request might request addressable elements 1 to 1000.
Techniques for efficiently managing this type of problem exist, depending on the type of system with in which it is encountered and the types of accesses which may be required. Such known techniques include:
1. Bit Maps using flags covering the entire addressable element space to indicate the existence of locks together with a supplementary system to monitor and identify the owners of the locks and, if necessary, to resolve overlapping range lock requests (principally applicable to small shared resources where overlapping requests are not present or occur infrequently);
2. Linked Lists containing information indicating the locked ranges and the owners of the locks (principally applicable to systems which are not highly interactive or where requests are not highly randomized or of great number and having a small number (e.g. less than 10,000) of shared files, a small (e.g. less than 600) number of processes, and in which response time is not critical (since search for conflicts through linked lists is an inherently slow procedure));
3. Individual addressable element locking in which each addressable element is viewed as an entity and separate lock information maintained (principally applicable where anticipated lock ranges are small); and
4. Rounding up which is similar to individual element locking except that the resource is divided into predetermined ranges, each of which is treated as a separate entity and extends the concept of individual addressable element locking to larger lock ranges.
While these known approaches and techniques have been adequate for particular systems and applications, none is generalized or capable of efficient application to a variety of systems and applications. All exhibit inherent inefficiencies such as hardware inefficiency imposed by bit maps and individual element locking or inefficiency of shared resource utilization where the rounding up technique results in the locking of a greater portion of the shared resource than is requested.